package q46

func permute(nums []int) [][]int {
	result:=[][]int{}
	for i,num:=range nums{

		re:=[]int{}

		if i==0 && i+1<len(nums){
			re=nums[i+1:]
		}else if i==len(nums)-1 && i>0{
			re=nums[:i]
			//fmt.Printf("===%v,%d,%v,%d\n",nums,num,re,i)
		}else if i>0 && i+1<len(nums){
			re=append(re,nums[:i]...)
			re=append(re,nums[i+1:]...)
		}
		//fmt.Printf("%v,%d,%v,%d\n",nums,num,re,i)

		pr:=permute(re)
		if len(pr)==0{
			result=append(result, []int{num})
		}else{
			for _,l:=range pr{
				l=append(l, num)
				result=append(result, l)
			}
		}
	}

	return result
}